#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int coinChange(vector<int>& coins, int amount) {
    int n = coins.size();
    vector<int> dp(amount + 1);

    for (int i = 1; i <= amount; ++i)
        dp[i] = 0x3f3f3f3f;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = coins[i - 1]; j <= amount; ++j)
        {
            dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
        }
    }

    dp[amount] = (dp[amount] == 0x3f3f3f3f) ? -1 : dp[amount];
    return dp[amount];
}

int main()
{

	return 0;
}